Batch 3 - Class 223 - Induction and Visualization

• Five school girls were weighed in pairs and found to be 129, 125, 124, 123, 122, 121, 120, 118, 116 and 114 pounds. How much do they weight individually?
• Answer: 56, 58, 60, 64, 65. Reasoning below
• All girls must weight different, otherwise there would be repetition in pair weights. Let weights be a>b>c>d>e. Then largest weight must be a+b, then a+c. Lightest must be e+d, and then e+c. Sum of all the pair wise weights is 4(a+b+c+d+e) = 1212, and hence (a+b+c+d+e) = 303. Now c = (a+b+c+d+e)- (a+b) - (d+e) = 1212 - 129 - 114 = 60. a+c = 125, and hence a = 65, and a+b = 129, so b = 64. Similarly the rest.

• How many squares does a 5x5 grid have? You have solved this problem before, but can you attempt it by induction? Can you generalize it for nxn square?

• A visual solution is to consider what all new squares are forming by adding another row and column. 

  

• On the 5x5 grid, we will now start from a particular square and try to visit every square without repeating a square. From any given square, you are allowed to go to one of the adjacent four squares. Hence a possible path is as under

• Try starting from a different position. Are you still able to traverse all the squares?
• Are there any starting positions for which you are unable to traverse the whole grid?
• Do you think if you tried other possible ways, you would get there? Try harder.
• Are there starting positions from which you think its impossible to traverse all squares? Can you prove that its impossible?
• Instructor Notes: Let kids work on the problem at this stage, and let them come up with their insights. Some may get to a pattern, some may not. If they don't, provide a hint for them to try and spot a pattern on which starting points are good versus bad. Note the application of symmetry in getting to the pattern.

• What does the pattern look like? Does it provide a hint into how to make a conclusive proof about the cells marked as question marks?
• Instructor Notes: At this stage, it is a bit of an epiphany. See if kids can get to checkerboard pattern. If they can, then provide them a hint to chessboard coloring. Second hint is to think about what happens to the color in each move. Third is to count number of black and white cells - ask kids to list the "paths" as sequence of black and white cells. That should do it.
• Back to Induction - What would happen in a 4x4 or a 6x6 grid? Does the fact that now you have equal number of black and white squares automatically imply that such a path is always possible?
• Answer: No. Ask students for an example of a grid where there are equal number of black and white squares, but a path is not possible. Answer: 6x1 strip
• Can you provide and an even square grid always has such paths from all starting positions?
• Hint: Use induction
• Answer: Essentially, starting from any position on outermost squares, one can complete the full outer round, and then enter inside - if a smaller even grid had solutions, this must as well. If you are starting from an inner starting square, do what you would do for n-2 grid. At some point in this solution you would be going along the "edge" of n-2 grid (note that this is mandatorily required to approach the corner of inside n-2 grid). This can be used as an opportunity to jump to outermost layer and complete that before coming back in.
• Why doesn't this apply for odd grids. For example, 1x1 grid has a trivial solution. Why doesn't that scale to all odd grids? See what happens when you go to 3x3. Here, starting on outermost and completing a full round, we have no point of entry to inner squares. We need at least 4 square-side to guarantee that. Induction can sometimes mislead, so be careful!
• Also note that the converse is not true. There could have been a solution to 5x5 even if solutions to 3x3 did not exist. So induction works one way only. This is because we go from n to n+1 in induction, and not from n+1 to n.
• Arjun had a stronger claim and a beautiful solution to this problem. The claim being that there is a loop across all squares, with one leg of the loop along a full side of the grid. Given the loop, you can start from any square and traverse the entire grid. Given the leg along a full side, you can construct the loop for (n+2)x(n+2) grid, given the loop for nxn grid as under.

• (Cornell) Two people have two consecutive natural numbers pasted on their heads, which they can't see but the other person can see. First person starts by asking the other if she knows what her number is. If she says yes, game ends. If she says no, she asks the first person if he knows his number. And so on. Does the game ever end? Sometimes? Never? Always?